package com.tingyuge.base.structrue.hash;

import java.util.HashMap;
import java.util.TreeMap;

/**
 * @Created by xiaodao
 */
public class Hash<K,V> {
    private TreeMap<K,V>[] hash;
    private int M;//初始容量.
    private int size;
    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private static final int initCapacity = 7;


    public Hash(int M){
        this.M = M;
        size=0;
        hash = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hash[i] =  new TreeMap<>();
            
        }

    }

    public Hash(){
        this(initCapacity);
    }

    private int getSize(){
        return size;
    }

    public int hash(K key){
        //取正符号 int是32 为 将首位变成0
        return key.hashCode() & 0x7fffffff %M;
    }

    public void add(K key,V value){
        TreeMap<K, V> map = this.hash[hash(key)];
        if(map.containsKey(key)){
            map.put(key,value);
        }else{
            map.put(key,value);
            size++;
            //超出 数组* treemap
            if(size  >= upperTol *M){
                resize(2 * M);
            }
        };
    }

    public V remove(K key){
        TreeMap<K, V> map = hash[hash(key)];
        V res = null;
        if(map.containsKey(key)){
            res = map.get(key);
            size--;
            if(size  >= lowerTol *M && M /2 >=initCapacity){
                resize(M /2 );
            }
        }
        return res;
    }


    public void set(K key,V value){
        TreeMap<K, V> map = hash[hash(key)];
        if(!map.containsKey(key)){
            throw  new IllegalArgumentException("key is not contian");
        }else{
            map.put(key,value);
        }
    }

    public boolean contains(K key){
        return hash[hash(key)].containsKey(key);
    }

    public V get(K key){
        TreeMap<K, V> map = hash[hash(key)];
        if(!map.containsKey(key)){
            throw  new IllegalArgumentException("key is not contian");
        }else{
            return map.get(key);
        }
    }



    /**
     * 扩容 缩容
     * @param newM
     */
    private void resize(int newM) {
        TreeMap<K,V>[] newHase = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            newHase[i] =  new TreeMap<>();
        }
        int oldM = M;
        this.M = newM;
        for (int i = 0; i < oldM; i++) {
            TreeMap<K,V> map = newHase[i];
            for (K key : map.keySet()) {
                newHase[hash(key)].put(key,map.get(key));
            }
            
        }
    }

    public static void main(String[] args) {
      String s1 = "zzz";
      String s2 = "zzz";
      String s3 = new String("zzz");
        System.out.println(s1 ==s2);
        System.out.println(s1==s3);
        String s4 = s3.intern();
        System.out.println(s1 ==s4);


    }

}
